#include "sudoku.h"
#include <time.h>
#include <stdlib.h>
#include <stdint.h>

int g_squareIndex[SUDOKU_HEIGHT][SUDOKU_WIDTH] = {
	{0,0,0,1,1,1,2,2,2},
	{0,0,0,1,1,1,2,2,2},
	{0,0,0,1,1,1,2,2,2},
	{3,3,3,4,4,4,5,5,5},
	{3,3,3,4,4,4,5,5,5},
	{3,3,3,4,4,4,5,5,5},
	{6,6,6,7,7,7,8,8,8},
	{6,6,6,7,7,7,8,8,8},
	{6,6,6,7,7,7,8,8,8}
};
struct point { int x; int y; };
struct point g_squarePoint[9][9] = {
	{ {0,0}, {1,0}, {2,0}, {0,1}, {1,1}, {2,1}, {0,2}, {1,2}, {2,2} },
	{ {3,0}, {4,0}, {5,0}, {3,1}, {4,1}, {5,1}, {3,2}, {4,2}, {5,2} },
	{ {6,0}, {7,0}, {8,0}, {6,1}, {7,1}, {8,1}, {6,2}, {7,2}, {8,2} },
	{ {0,3}, {1,3}, {2,3}, {0,4}, {1,4}, {2,4}, {0,5}, {1,5}, {2,5} },
	{ {3,3}, {4,3}, {5,3}, {3,4}, {4,4}, {5,4}, {3,5}, {4,5}, {5,5} },
	{ {6,3}, {7,3}, {8,3}, {6,4}, {7,4}, {8,4}, {6,5}, {7,5}, {8,5} },
	{ {0,6}, {1,6}, {2,6}, {0,7}, {1,7}, {2,7}, {0,8}, {1,8}, {2,8} },
	{ {3,6}, {4,6}, {5,6}, {3,7}, {4,7}, {5,7}, {3,8}, {4,8}, {5,8} },
	{ {6,6}, {7,6}, {8,6}, {6,7}, {7,7}, {8,7}, {6,8}, {7,8}, {8,8} }
};

int sudoku_get_mask(struct sudoku* sudoku, int x, int y)
{
	int mask = 0x1FF;
	for(int cx = 0; cx < 9; ++cx){
		mask &= (sudoku->grid[y][cx] == 0 ? mask : ~(1 << (sudoku->grid[y][cx]-1)));
	}
	for(int cy = 0; cy < 9; ++cy){
		mask &= (sudoku->grid[cy][x] == 0 ? mask : ~(1 << (sudoku->grid[cy][x]-1)));
	}
	int idx = g_squareIndex[y][x];
	struct point pt = {0,0};
	for(int c = 0; c < 9; ++c){
		pt = g_squarePoint[idx][c];
		mask &= (sudoku->grid[pt.y][pt.x] == 0 ? mask : ~(1 << (sudoku->grid[pt.y][pt.x]-1)));
	}
	return mask;
}

struct sudoku* sudoku_generate(struct sudoku* sudoku, int number_knowns)
{
	unsigned long long t = time(NULL);
	srand(t);
	t = (t+rand())*(t+time(NULL));
	srand(t+(rand()*rand()));
	
	sudoku_reset(sudoku);
	sudoku_solve(sudoku);
	
	int unknowns = 81 - number_knowns;
	int x, y;
	char tmp;
	while(unknowns--){
		do{
			x = rand() % 9;
			y = rand() % 9;
		} while( sudoku->grid[y][x] == 0 );
		
		tmp = sudoku->grid[y][x];
		sudoku->grid[y][x] = 0;
		if( sudoku_is_unique(sudoku) != 1 ){
			unknowns++;
			sudoku->grid[y][x] = tmp;
		}
	}
	
	return NULL;
}

void sudoku_reset(struct sudoku* sudoku)
{
	memset(sudoku, 0, sizeof(*sudoku));
}

// taken from http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer
// don't ask me how it works...
int NumberOfSetBits(int i)
{
	i = i - ((i >> 1) & 0x55555555);
	i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
	return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

int sudoku_is_atomic(struct sudoku* sudoku, int x, int y, char* val)
{
	int mask = 0x1FF;
	// check row
	for(int cx = 0; cx < 9; ++cx){
		if( cx != x ) mask &= (sudoku->grid[y][cx] == 0 ? mask : ~(1 << (sudoku->grid[y][cx]-1)));
	}
	// check column
	for(int cy = 0; cy < 9; ++cy){
		if( cy != y ) mask &= (sudoku->grid[cy][x] == 0 ? mask : ~(1 << (sudoku->grid[cy][x]-1)));
	}
	// check square
	int square = g_squareIndex[y][x];
	struct point p = {0,0};
	for(int c = 0; c < 9; ++c){
		p = g_squarePoint[square][c];
		if( !(p.x == x && p.y == y) ) mask &= (sudoku->grid[p.y][p.x] == 0 ? mask : ~(1 << (sudoku->grid[p.y][p.x]-1)));
	}
	if( !mask ) return 0; // this should never happen. there should always be a solution.
	if( NumberOfSetBits(mask) != 1 ) return 0; // not atomic...
	
	// save the value if needed
	if( val ){
		for(int i = 0; i < 9; ++i){
			if( mask == (1<<i) ){ *val = (char)(i+1); break; }
		}
	}
	
	return 1;
}

int sudoku_is_solved(struct sudoku* sudoku)
{
	if(!sudoku) return 0;

	struct sudoku test = *sudoku;
	sudoku_solve(&test);
	if( memcmp(&test, sudoku, sizeof(struct sudoku)) == 0 ) return 1;
	
	return 0;
}

int sudoku_solve(struct sudoku* sudoku)
{
	if(!sudoku) return 0;
	
	int mask = 0x1ff;
	int best_x = 0, best_y = 0;
	int best_mask = 0x2ff;
	
	
	for(int y = 0; y < 9; ++y){
		for(int x = 0; x < 9; ++x){
			if( sudoku->grid[y][x] != 0 ) continue;
			mask = sudoku_get_mask(sudoku, x, y);
			if( mask < best_mask ){
				best_mask = mask;
				best_x = x;
				best_y = y;
			}
		}
	}
	
	if( best_mask == 0x2ff ) return 1; // this puzzle is already solved!
	
	if( best_mask == 0x000 ) return 0; // this puzzle can't be solved!

	int start_c = rand() % 9;
	int c = start_c;
	do{
		if( (best_mask & (1<<c)) ){
			sudoku->grid[best_y][best_x] = c+1;
			if( sudoku_solve(sudoku) ) return 1;
		}
		c = (c+1) % 9;
	} while( c != start_c );
	
	sudoku->grid[best_y][best_x] = 0;
	
	
	return 0;
}

int sudoku_is_unique(struct sudoku* pSudoku)
{
	struct sudoku sudoku = *pSudoku; // create a copy first!!!
	return _sudoku_is_unique(&sudoku);
}

int _sudoku_is_unique(struct sudoku* sudoku)
{
	if(!sudoku) return 0;
	
	unsigned short mask = 0x1ff;
	int best_x = 0, best_y = 0;
	unsigned short best_mask = 0x2ff;
	
	
	for(int y = 0; y < 9; ++y){
		for(int x = 0; x < 9; ++x){
			if( sudoku->grid[y][x] != 0 ) continue;
			mask = 0x1FF;
			// check row
			for(int cx = 0; cx < 9; ++cx){
				mask &= (sudoku->grid[y][cx] == 0 ? mask : ~(1 << (sudoku->grid[y][cx]-1)));
			}
			// check column
			for(int cy = 0; cy < 9; ++cy){
				mask &= (sudoku->grid[cy][x] == 0 ? mask : ~(1 << (sudoku->grid[cy][x]-1)));
			}
			// check square
			int square = g_squareIndex[y][x];
			struct point p = {0,0};
			for(int c = 0; c < 9; ++c){
				p = g_squarePoint[square][c];
				mask &= (sudoku->grid[p.y][p.x] == 0 ? mask : ~(1 << (sudoku->grid[p.y][p.x]-1)));
			}
			
			if( mask < best_mask ){
				best_mask = mask;
				best_x = x;
				best_y = y;
			}
		}
	}
	
	if( best_mask == 0x2ff ) return 1; // this puzzle is already solved!
	
	if( best_mask == 0x000 ) return 0; // this puzzle can't be solved!

	int nsolutions = 0;
	for(int c = 0; c < 9; ++c){
		if( (best_mask & (1<<c)) ){
			sudoku->grid[best_y][best_x] = c+1; // try this value
			
			switch( _sudoku_is_unique(sudoku) )
			{
				case 1: // unique
					nsolutions++;
				case 0: // no solution
					break;
				case 2: // not unique
					return 2;
			}
			
			if( nsolutions > 1 ) return 2;
			//if( sudoku_solve(sudoku) ) return 1; // aaaannnnndddd... here comes recursion! :)
		}
	}
	
	sudoku->grid[best_y][best_x] = 0;
	
	if( nsolutions > 1 ) return 2;
	return nsolutions; // either zero or one
}

int sudoku_bad_square(struct sudoku* sudoku, int x, int y)
{
	for(int cx = 0; cx < 9; ++cx){
		if( cx != x && sudoku->grid[y][cx] == sudoku->grid[y][x] ) return 1;
	}
	for(int cy = 0; cy < 9; ++cy){
		if( cy != y && sudoku->grid[cy][x] == sudoku->grid[y][x] ) return 1;
	}
	int idx = g_squareIndex[y][x];
	struct point p;
	for(int c = 0; c < 9; ++c){
		p = g_squarePoint[idx][c];
		if( p.y == y && p.x == x ) continue;
		if( sudoku->grid[p.y][p.x] == sudoku->grid[y][x] ) return 1;
	}
	
	return 0;
}

int sudoku_save(struct sudoku* sudoku, struct sudoku* original, const char* file_name)
{
	FILE* filp = fopen(file_name, "wb");
	if(!filp){
		return -1;
	}
	
	char zero = 0;
	
	for(int row = 0; row < 9; ++row){
		for(int col = 0; col < 9; ++col){
			fwrite(&sudoku->grid[col][row], 1, 1, filp);
			if( original )
				fwrite(&original->grid[col][row], 1, 1, filp);
			else
				fwrite(&zero, 1, 1, filp);
		}
	}
	
	fclose(filp);
	
	return 0;
}

int sudoku_load(struct sudoku* sudoku, struct sudoku* original, const char* file_name)
{
	FILE* filp = fopen(file_name, "rb");
	if(!filp){
		return -1;
	}
	
	char zero = 0;
	
	for(int row = 0; row < 9; ++row){
		for(int col = 0; col < 9; ++col){
			fread(&sudoku->grid[col][row], 1, 1, filp);
			if( original )
				fread(&original->grid[col][row], 1, 1, filp);
			else
				fread(&zero, 1, 1, filp);
		}
	}
	
	fclose(filp);
	
	return 0;
}